﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_838_PushDominoes
{
    class MainProject
    {
        static void Main(string[] args)
        {
            string dominoes = ".L.R...LR..L..";
            Console.WriteLine(PushDominoes(dominoes));
            //Console.WriteLine(IsPalindrome(1000021));
            Console.ReadKey();
        }
        public static string PushDominoes(string dominoes)
        {
            List<char> list = dominoes.ToList();
            //BFS
            Queue<int> que = new Queue<int>();
            for (int i = 0; i < list.Count; i++) if (list[i] != '.') que.Enqueue(i);
            Dictionary<int, int> dic = new Dictionary<int, int>(list.Count);
            for (int i = 0; i < list.Count; i++)
            {
                dic.Add(i,0);
            }
            while (que.Count > 0)
            {
                int size = que.Count;
                for (int i = 0; i < size; i++)
                {
                    if (que.Count<=0) break;

                    int index = que.Dequeue();

                    if (list[index] == 'L')
                    {
                        if (index - 1 >= 0)
                        {
                            if (list[index-1]=='R' || list[index - 1] == '.')
                            {
                                dic[index - 1] -= 1;
                                List<int> l = que.ToList();
                                if (l.Contains(index - 1))
                                {
                                    l.Remove(index - 1);
                                    que.Clear();
                                    foreach (var item in l) que.Enqueue(item);

                                }
                                else
                                {
                                    que.Enqueue(index - 1);
                                }
                            }
                           
                        }
                    }
                    else if (list[index] == 'R')
                    {
                        if (index + 1 < list.Count)
                        {
                            if (list[index + 1] == 'L' || list[index + 1] == '.')
                            {
                                dic[index + 1] += 1;
                                List<int> l = que.ToList();
                                if (l.Contains(index + 1))
                                {
                                    l.Remove(index + 1);
                                    que.Clear();
                                    foreach (var item in l) que.Enqueue(item);
                                }
                                else
                                {
                                    que.Enqueue(index + 1);
                                }
                            }
                        }
                    }
                    else
                    {
                        Console.WriteLine("Error");
                    }
                }

                foreach (var item in dic)
                {
                    if (item.Value == 1)
                    {
                        list[item.Key] = 'R';
                    }
                    else if(item.Value == -1)
                    {
                        list[item.Key] = 'L';
                    }
                }
                for (int i = 0; i < dic.Count; i++)
                {
                    dic[i] = 0;
                }
            }
            string str = string.Empty;
            foreach (var item in list)
            {
                str += item.ToString();
            }
            return str;
        }
    }
}
